package pers.vic.basics.datastructure.tree;

import com.sun.org.apache.xpath.internal.WhitespaceStrippingElementMatcher;
import jdk.nashorn.internal.ir.WhileNode;
import sun.net.www.protocol.http.HttpURLConnection;

import java.util.Objects;
import java.util.function.Consumer;

/**
 * @author Vic.xu
 * @description:二叉搜索树，是有序的
 * @date: 2020/10/27 0027 9:37
 */
public class BinarySearchTree implements TreeInterface {

    private BinaryNode root;

    public BinaryNode getRoot() {
        return root;
    }

    public void setRoot(BinaryNode root) {
        this.root = root;
    }

    @Override
    public BinaryNode find(Object key) {
        BinaryNode current = root;
        while (current != null) {
            if (Objects.equals(current.getData(), key)) {
                return current;
            }
            if (gt(current.getData(), key)) {
                current = current.getLeft();
            } else {
                current = current.getRight();
            }
        }
        return null;
    }

    @Override
    public boolean insert(Object key) {
        BinaryNode node = new BinaryNode(key);
        if (root == null) {
            this.root = node;
            return true;
        }

        BinaryNode current = root;
        BinaryNode parent = null;
        while (current != null) {
            parent = current;

            //放到左边
            if (gt(current.getData(), key)) {
                current = current.getLeft();
                if (current == null) {
                    node.setParent(parent);
                    parent.setLeft(node);
                    return true;
                }
            } else {
                current = current.getRight();
                if (current == null) {
                    node.setParent(parent);
                    parent.setRight(node);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 删除节点
     * 1. 没有节点：找到父节点的引用置为null
     * 2. 只有一个节点：父节点的原引用指向其子节点
     * 3. 有两个子节点：找到前驱节点或者后继节点（删除）覆盖当前节点
     * 前驱：左子树的最右节点
     * 后继：右子树的最左节点
     *
     * @param key data
     * @return true | false
     */
    @Override
    public boolean delete(Object key) {
        BinaryNode current = find(key);
        if (current == null) {
            return false;
        }
        BinaryNode parent = current.getParent();
        //根节点
        if (parent == null) {
            this.root = null;
            return true;
        }

        //当前节点是否是父节点的左节点
        boolean isLeftNode = Objects.equals(key, parent.getLeft() == null  ? null : parent.getLeft().getData());
        //父节点set节点的set方法
        Consumer<BinaryNode> parentSet = isLeftNode ? parent::setLeft : parent::setRight;
        //1、没有节点  0度
        if (current.getLeft() == null && current.getRight() == null) {
            parentSet.accept(null);
            return true;
        }
        //2 有一个节点，且是右节点 1度    把右节点设置给父节点
        if (current.getLeft() == null && current.getRight() != null) {
            parentSet.accept(current.getRight());
            current.getRight().setParent(parent);
            return true;
        }
        //3 有一个节点，且是左节点 1度    把左节点设置给父节点
        if (current.getLeft() != null && current.getRight() == null) {
            parentSet.accept(current.getLeft());
            current.getLeft().setParent(parent);
            return true;
        }
        // 4 有两个子节点 2 度， 则找到前驱(或后继)节点，用后继节点覆盖当前节点，然后删除当前节点
        if (current.getRight() != null && current.getLeft() != null) {
            //此处查找前驱节点：左子树的最右节点
            BinaryNode precursor = current.getLeft();
            while (precursor.getRight() != null) {
                precursor = precursor.getRight();
            }
            //说明是某个节点的右节点,则把对应的前驱节点 从它的父节点中删除
            if (precursor != current.getLeft()) {
                precursor.getParent().setRight(null);
            }
            // 用前驱节点覆盖当前节点
            parentSet.accept(precursor);
            precursor.setParent(parent);

            //覆盖
            precursor.setLeft(current.getLeft());
            precursor.setRight(current.getRight());
            current.setParent(null);
            current.getRight().setParent(precursor);
            current.getLeft().setParent(precursor);
            return true;
        }


        return false;
    }

    /**
     * 中序：左根右
     */
    @Override
    public void infixOrder() {
        infixOrder(root);
    }

    /**
     * 中序：左根右
     */
    public void infixOrder(BinaryNode node) {
        if (node != null) {
            infixOrder(node.getLeft());
            System.out.print(node.getData() + " ");
            infixOrder(node.getRight());
        }
    }

    /**
     * 前序遍历：根→左→右
     */
    @Override
    public void preOrder() {
        preOrder(root);
    }

    public void preOrder(BinaryNode node) {
        if (node != null) {
            System.out.print(node.getData() + " ");
            preOrder(node.getLeft());
            preOrder(node.getRight());
        }
    }

    /**
     * 后序遍历：左→右→根
     */
    @Override
    public void postOrder() {
        postOrder(root);
    }

    /**
     * 后序遍历：左→右→根
     */
    public void postOrder(BinaryNode node) {
        if (node != null) {
            postOrder(node.getLeft());
            postOrder(node.getRight());
            System.out.print(node.getData() + " ");
        }
    }

    /**
     * 最大：最右节点
     */
    @Override
    public BinaryNode max() {
        BinaryNode current = root;
        BinaryNode max = null;
        while (current != null) {
            max = current;
            current = current.right;
        }
        return max;
    }

    public boolean gt(Object o1, Object o2) {
        return String.valueOf(o1).compareTo(String.valueOf(o2)) > 0;
    }

    @Override
    public BinaryNode min() {
        BinaryNode current = root;
        BinaryNode min = null;
        while (current != null) {
            min = current;
            current = current.left;
        }
        return min;
    }
}
